The present invention is in the field of data processing and, in particular, relates to high speed auxiliary memories.
An architecture called virtual memory is employed in many data processing systems where service is provided to a number of users. Typically, virtual memory is divided into segments, each of which is further divided into pages with each page accomodating a predetermined maximum number of words. In a number of systems, for example the Series 50 systems manufactured by Prime Computer, Inc. of Natick, Mass., the addresses of the segments and pages are allocated by an operating system and can be arranged in a medium density physical memory in a random fashion. To the user, however, an appearance of continuity and unlimited memory space is presented and the user need not be concerned with the actual interleaved nature of programs in the main memory.
Because of the distributed reality of programs within the physical memory as well as the time and energy necessary to retrieve data from the memory, it is also preferred to employ a smaller auxiliary memory or data cache to store data which is likely to be needed by the user at a particular time. For this purpose, a data cache formed from Random Access Memory (RAM) units is often employed. One convenient method for loading a data cache is to store data according to the lower order virtual address bits. For example, in a small data cache an entry at location 5 of a user's virtual page will be stored at location 5 in the data cache. However, this scheme alone does not assure that data retrieved from a particular location in the cache will be valid because data from two or more users can be assigned the same virtual address and a small data cache loaded in this fashion may not distinguish between the virtual pages of multiple users.
In order to validate data from the cache, an address translation is performed using an address tag (which is obtained along with the data from the cache when it is accessed) and an address translation element which is also most often implemented in RAM hardware. One known structure is called a lookaside buffer and essentially operates by storing main memory addresses and confirmation tags. When the lookaside buffer is accessed with a virtual address, it returns a physical address and a tag to confirm the virtual address. If the physical address in the lookaside buffer does not match the address tag associated with the data, a data cache miss occurs (i.e., the data in the cache is from a different page) and the physical address from the lookaside buffer is used to retrieve the proper data from the main memory.
Periodically, it is necessary to purge the address translation element because the physical locations of the data in the medium density memory are changed. For example, when all the pages in the medium density memory are allocated, pages must be loaded out to a higher density physical memory such as a disk. When this occurs, the translation element may contain stale entries. Since selective revision of the entries in the address translation element is very time consuming (because all the entries must undergo a comparison to determine locations to be invalidated), it typically is more efficient to purge the translation element altogether. However, purging of the translation element is also time-consuming, albeit less so than selective revision, since a write command must be executed for each entry in a lookaside buffer or equivalent translation element. In systems that employ large translation buffers (e.g. 128 or more locations), purging can have a serious effect on system performance.
There exists a need for better address translation systems. In particular, a system that eliminates or reduces the penalty for complete purging of buffers or similar elements storing virtual-to-physical address translations would satisfy a long felt need in the industry.